package com.sheng.leetcode.year2022.month10.day10;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/10/10
 *<p>
 * 801. 使序列递增的最小交换次数<p>
 *<p>
 * 我们有两个长度相等且不为空的整型数组nums1和nums2。在一次操作中，我们可以交换nums1[i]和nums2[i]的元素。<p>
 * 例如，如果 nums1 = [1,2,3,8] ， nums2 =[5,6,7,4] ，你可以交换 i = 3 处的元素，<p>
 * 得到 nums1 =[1,2,3,4] 和 nums2 =[5,6,7,8] 。<p>
 * 返回 使 nums1 和 nums2 严格递增所需操作的最小次数 。<p>
 * 数组arr严格递增 且 arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1]。<p>
 *<p>
 * 注意：<p>
 * 用例保证可以实现操作。<p>
 *<p>
 * 示例 1:<p>
 * 输入: nums1 = [1,3,5,4], nums2 = [1,2,3,7]<p>
 * 输出: 1<p>
 * 解释:<p>
 * 交换 A[3] 和 B[3] 后，两个数组如下:<p>
 * A = [1, 3, 5, 7] ， B = [1, 2, 3, 4]<p>
 * 两个数组均为严格递增的。<p>
 *<p>
 * 示例 2:<p>
 * 输入: nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9]<p>
 * 输出: 1<p>
 *<p>
 * 提示:<p>
 * 2 <= nums1.length <= 10^5<p>
 * nums2.length == nums1.length<p>
 * 0 <= nums1[i], nums2[i] <= 2 * 10^5<p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/minimum-swaps-to-make-sequences-increasing">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode0801 {

    @Test
    public void test01() {
//        int[] nums1 = {1,3,5,4}, nums2 = {1,2,3,7};
        int[] nums1 = {0,3,5,8,9}, nums2 = {2,1,4,6,9};
        System.out.println(new Solution().minSwap(nums1, nums2));
    }
}
class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        // n 为数组长度
        int n = nums1.length;
        int[][] f = new int[n][2];
        // 为数组 f 赋初值为 n + 10
        for (int i = 1; i < n; i++) {
            f[i][0] = f[i][1] = n + 10;
        }
        // 将数组的第一个元素设置为 1
        f[0][1] = 1;
        // 循环
        for (int i = 1; i < n; i++) {
            // 如果数组 nums1 中 后一个元素比前一个元素大，并且在 nums2 数组中也是一样的
            if (nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1]) {
                // 在 i 位置的 0 处，将前元素的值赋值给当前元素，在 1 处，将前元素的值加 1 后赋值给当前元素
                f[i][0] = f[i - 1][0];
                f[i][1] = f[i - 1][1] + 1;
            }
            // 如果数组 nums1 的后一个元素大于 nums2 的前一个元素，并且 nums2 的后一个元素大于 nums1 的前一个元素
            if (nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1]) {
                f[i][0] = Math.min(f[i][0], f[i - 1][1]);
                f[i][1] = Math.min(f[i][1], f[i - 1][0] + 1);
            }
        }
        return Math.min(f[n - 1][0], f[n - 1][1]);
    }
}
